package org.example.sword2offer.primary;

import java.util.Stack;

/**
 * @author: lynn
 * @Descript: NC52_ 括号序列号
 * @date: 2021/7/7 18:03
 * @version: 1.0
 */
public class Q83_Brackets {
    public static void main(String[] args) {
        Q83_Brackets brackets=new Q83_Brackets();
        Boolean b=brackets.isValid("{([])}");
        System.out.println(Boolean.toString(b));
    }

    // 给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列
    // 括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法

    public boolean isValid (String s) {
        Stack<Character> st=new Stack<>();
        //思路是将'(','{','[' 入堆
        for(int i = 0; i < s.length(); i++){
            if (s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{') st.push(s.charAt(i));
            else{
                if (st.isEmpty()) return false;
                if (s.charAt(i) == ')' && st.peek() != '(') return false;
                else if (s.charAt(i) == ']' && st.peek() != '[') return false;
                else if (s.charAt(i) == '}' && st.peek() != '{') return false;
                st.pop();
            }
        }
        return st.empty() ? true : false;
    }
}
